package com.test.daily.leetcode.y2021.m12.day1219;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author Tom on 2021/12/19
 */
public class Code01_FindJudge {
    public static void main(String[] args) {
        Code01_FindJudge cf = new Code01_FindJudge();
        int n = 4;
        int[][] trust = new int[][]{{1, 3}, {1, 4}, {2, 3}, {2, 4}, {4, 3}};
        System.out.println(cf.findJudge1(n, trust));
    }

    public int findJudge(int n, int[][] trust) {
        if (trust == null || trust.length < 1) {
            return n == 1 ? 1 : -1;
        }
        int[] trustCount = new int[n + 1];
        boolean[] trustOther = new boolean[n + 1];
        for (int i = 0; i < trust.length; i++) {
            trustOther[trust[i][0]] = true;
            trustCount[trust[i][1]]++;
        }
        int first = 0;
        int second = 0;
        for (int i = 0; i <= n; i++) {
            if (trustCount[i] > trustCount[first]) {
                first = i;
            } else if (trustCount[i] > trustCount[second]) {
                second = i;
            }
        }
        return trustCount[first] == n - 1 && trustCount[first] > trustCount[second] && !trustOther[first] ? first : -1;
    }

    public int findJudge1(int n, int[][] trust) {
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for(int[] edge: trust){
            int x = edge[0];
            int y = edge[1];
            inDegree[y]++;
            outDegree[x]++;
        }
        for(int i = 1; i <= n; i++){
            if(inDegree[i] == n -1 && outDegree[i] == 0){
                return i;
            }
        }
        return -1;
    }
}
